#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;


//dp题
// class NumMatrix {
// public:
//     NumMatrix(vector<vector<int>>& matrix) {
//         int row  = matrix.size();
//         int column = matrix[0].size();
    
//         if(row==1&&(column==0||column==1)){
            
//         }
//         else{
       
//         dp  = vector<vector<int>>(row, vector<int>(column,0));
        
//         //初始化一波
//         dp[0][0] = matrix[0][0];
//         for(int i = 1;i<column;++i){
//             dp[0][i] = dp[0][i-1]+matrix[0][i];
//         }
//         for(int i = 1;i<row;++i){
//             dp[i][0] = dp[i-1][0]+matrix[i][0];
//         }
//         for(int i = 1;i<row;++i){
//             for(int j = 1;j<column;++j){
//                 dp[i][j] = matrix[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
//             }
//         }
//         }
//     }
    
//     int sumRegion(int row1, int col1, int row2, int col2) {
//         int first = 0;
//         int status1 = 0;
//         int second = 0;
//         int status2 = 0;
//         int tree = 0;
//         if(dp.empty()){
//             return 0;
//         }
        
//         if(row1-1>=0){
//             first = dp[row1-1][col2];
//             status1 = 1;
//         }
//         if(col1-1>=0){
//             second = dp[row2][col1-1];
//             status2  = 1;
//         }

//         int result = 0;
//         if(status1==0||status2==0){
//             result = dp[row2][col2]-first-second;
//         }
//         else{
//             result = dp[row2][col2]-first-second+dp[row1-1][col1-1];
//         }
//         return result;
//     }

// public:
//     vector<vector<int>> dp={0,vector<int>(0,0)};

// };


class NumMatrix {
public:
    vector<vector<int>> sums;

    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m > 0) {
            int n = matrix[0].size();
            sums.resize(m, vector<int>(n + 1));
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i][j + 1] = sums[i][j] + matrix[i][j];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            sum += sums[i][col2 + 1] - sums[i][col1];
        }
        return sum;
    }
};


/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */


int main(){
    vector<vector<int>> matrix = {{3, 0, 1, 4, 2},
  {5, 6, 3, 2, 1},
  {1, 2, 0, 1, 5},
  {4, 1, 0, 1, 7},
  {1, 0, 3, 0, 5}};
//    vector<vector<int>> matrix = {{{}}};
    NumMatrix num(matrix);
    cout<<num.sumRegion(1,1,2,2)<<endl;
}